package com.klun.project.common.constans.leetcode;


/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 */
public class Solution5 {

	public String longestPalindrome1(String s) {
		// i 和 j 左右两侧相同则+2 找出最长路径
		return null;
	}


	// 动态规划使用数组或者二维数组
	public String longestPalindrome(String s) {
		int len = s.length();
		if (len < 2) {
			return s;
		}
		int maxLen = 1;
		int begin = 0;
		// dp[i][j] 表示s[i,j] 是否是回文串
		boolean[][] dp = new boolean[len][len];
		for (int i = 0; i < len; i++) {
			dp[i][i] = true;
		}
		char[] charArray = s.toCharArray();
		for (int l = 2; l <= len; l++) {
			for (int i = 0; i < len; i++) {
				int j = l + i - 1; // 确定右边界
				if (j >= len) {
					break;
				}
				if (charArray[i] != charArray[j]) {
					dp[i][j] = false;
				} else {
					if (j - i < 3) {
						dp[i][j] = true;
					} else {
						dp[i][j] = dp[i + 1][j - 1];
					}
				}
				if (dp[i][j] && j - i + 1 > maxLen) {
					maxLen = j - i + 1;
					begin = i;
				}
			}
		}
		return s.substring(begin, begin + maxLen);
	}

	public static void main(String[] args) {
		Solution5 solution = new Solution5();
		String res = solution.longestPalindrome("sdafewagwertagfdsfaf");
		System.out.println(res);
	}


}
